package com.wk.data;

import java.util.HashMap;

/**
 * hashmap 实现前缀树
 */
public class TrieTree {

	private class Node{
		public HashMap<Character, Node> childs;
		// 是否是一个字符串的末尾节点
		public boolean isLeaf;
		//有多少字符串经过当前节点（以当前为前缀的字符串数）
        public int paths = 0;

		public Node() {
			this.childs = new HashMap<Character, TrieTree.Node>();
			this.isLeaf = false;
		}	
	}
	public static void main(String[] args) {
		String[] arr1 = {"abc", "bch", "hodf", "hdfos"};
        String[] arr2 = {"bch", "ho", "h", "hd","df"};
        
        TrieTree trieTree = new TrieTree();
        for (String word : arr1) {
			trieTree.insert(word);
		}
        // arr2中有哪些字符，是arr1中出现的？请打印
        for (String word : arr2) {
			if(trieTree.search(word)) {
				System.out.println(word);
			}
		}
        System.out.println("=======================");
        //arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印
        for (String word : arr2) {
			if(trieTree.startWith(word)) {
				System.out.println(word);
			}
		}
        System.out.println("=======================");
        //arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印arr2中出现次数最大的前缀。
        for (String word : arr2) {
			
			System.out.println(word+":"+trieTree.getPrefixTimes(word));
			
		}
	}
	Node root;

	public TrieTree() {
		root = new Node();
	}
	/**
	 * 插入单词
	 * @param word
	 */
	public void insert(String word) {
		if(word == null || word.length() == 0) {
			return;
		}
		char[] charArray = word.toCharArray();
		insert(root,charArray,0);
		
	}
	public void insert(Node node,char[] charArray,int index) {
		if(index >= charArray.length) {
			return;
		}
		Node curNode = node;
		if(!curNode.childs.containsKey(charArray[index])) {
			curNode.childs.put(charArray[index], new Node());	
		}
		curNode = curNode.childs.get(charArray[index]);
		curNode.paths++;
		if(index == charArray.length-1) {
			curNode.isLeaf = true;
		}
		
		index++;
		insert(curNode,charArray,index);
	}
	public void insert2(String word) {
		insert2(root,word);
		
	}
	public void insert2(Node node,String word) {
		if(word == null || word.length() == 0) {
			return;
		}
		char[] charArray = word.toCharArray();
		Node curNode = node;
		for (int i = 0; i < charArray.length; i++) {
			if(!curNode.childs.containsKey(charArray[i])) {
				curNode.childs.put(charArray[i], new Node());
			}
			curNode = curNode.childs.get(charArray[i]);
			curNode.paths++;
		}
		curNode.isLeaf = true;
	}
	/**
	 * 是否插入过word
	 * @return
	 */
	public boolean search(String word) {
		if(word == null || word.length() == 0) {
			return false;
		}
		char[] charArray = word.toCharArray();
		Node curNode = root;
		for (char c : charArray) {
			if(!curNode.childs.containsKey(c)) {
				return false;
			}
			curNode = curNode.childs.get(c);
		}
		return curNode.isLeaf;
	}
	public boolean startWith(String word) {
		if(word == null || word.length() == 0) {
			return false;
		}
		char[] charArray = word.toCharArray();
		Node curNode = root;
		for (char c : charArray) {
			if(!curNode.childs.containsKey(c)) {
				return false;
			}
			curNode = curNode.childs.get(c);
		}
		return true;
	}
	public int getPrefixTimes(String word) {
		if(word == null || word.length() == 0) {
			return 0;
		}
		char[] charArray = word.toCharArray();
		Node curNode = root;
		for (char c : charArray) {
			if(!curNode.childs.containsKey(c)) {
				return 0;
			}
			curNode = curNode.childs.get(c);
		}
		return curNode.paths;
	}
}
